package Algorithm.KMP;

/*
详见笔记ppt
 */

public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
    }

    /***
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表 子串对应的部分匹配表
     * @return -1即为没有匹配到 否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        //遍历
        for (int i = 0, j = 0 ; i < str1.length() ; i++) {

            //需要处理str1.charAt(i) != str2.charAt(j) 去调整j的大小
            //KMP算法的核心
            while (j > 0 && str1.charAt(i) == str2.charAt(j)) {
                j = next[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {//找到了
                return i - j + 1;
            }
        }
        return -1;
    }

    //获取到一个字符串(子串)的部分匹配值表
    public static int[] kmpNext(String dest) {
        //创建一个next数组保存部分匹配值
        int[] next = new int[dest.length()];
        //如果字符串是长度为1 那么前缀和后缀都为空 则此时匹配值就为0 也即无论子串长度是多少 next[0]一定是0
        next[0] = 0;
        //用i对整个字符串进行扫描
        for (int i = 1, j = 0 ; i < dest.length() ; i++) {
            //当dest.charAt(i) != dest.charAt(j)时 我们需要从next[j-1]获取新的j
            //知道我们发现有dest.charAt(i) == dest.charAt(j)成立时才退出
            //这是kmp算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                //遇到不匹配的值时 获取到当前不匹配的值的前一位对应的匹配值表 重置该匹配值(停留在原来匹配到的最后一个字符上面)
                j = next[j - 1];
            }

            //当dest.charAt(i) == dest.charAt(j)满足时 部分匹配值就是要+1
            /*
            自己的理解:
            先保持j指针不动 i指针每次后移
            若匹配到相同的值 将j的值自增1 然后放到匹配值的i的位置上
             */
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
